#include "Configuration.h"
#include "Log.h"

#define DEFAULT_CAPACITY 8
#define LOAD_FACTOR   0.75
#define MAX_LINE 1024

void configuration_init(Configuration* map)
{
    map->table = NULL;
    map->size = 0;
    map->capacity = 0;
    map->hashseed = 0;
}

void configuration_load(Configuration* conf, const char* file)
{
    FILE* fp = fopen(file, "r");
    if (!fp) {
        log_error("open configuration file failed");        
        return ;
    }
    char line[MAX_LINE];
    while (fgets(line, MAX_LINE, fp)) {
        char* key = strtok(line, " \t\n=");
        char* val = strtok(NULL, " \t\n=");
        configuration_put(conf, key, val);
    }
    fclose(fp);
}

void configuration_destroy(Configuration* map)
{
    if (map->table == NULL) return;		/* 安全检查：如果 table 为 NULL, 则直接返回 */
    /* 销毁一个一个结点 */
    for (size_t i = 0; i < map->capacity; i++) {
        Entry* curr = map->table[i];		/* 获取链表的第一个结点 */
        while (curr) {
            Entry* next = curr->next;	/* 保存下一个结点 */
            free(curr->key);
            free(curr->val);
            free(curr);					/* 销毁当前结点 */
            curr = next;
        }
    }
    free(map->table);	/* 销毁 table 数组 */
    configuration_init(map);	/* 将 map 至于初始化状态 */
}

// murmurhash2: 
// 1. 对任意类型的key计算哈希值
// 2. 尽管key相同，但seed不同，哈希值不同。安全
static uint32_t hash(const void* key, int len, uint32_t seed) 
{
    const uint32_t m = 0x5bd1e995;
    const int r = 24;
    uint32_t h = seed ^ len;
    const unsigned char* data = (const unsigned char*)key;

    while (len >= 4) {
        uint32_t k = *(uint32_t*)data;

        k *= m;
        k ^= k >> r;
        k *= m;

        h *= m;
        h ^= k;

        data += 4;
        len -= 4;
    }

    switch (len) 
    {
    case 3: h ^= data[2] << 16;
    case 2: h ^= data[1] << 8;
    case 1: h ^= data[0];
            h *= m;
    }

    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return h;
}

static void rehash(Entry* curr, Entry** new_table, int new_capacity, uint32_t seed)
{
    // 重新计算 key 的哈希值，因为哈希种子变了
    uint32_t h = hash(curr->key, strlen(curr->key), seed);
    // 计算 key 在新数组 new_table 中的位置
    int idx = h % new_capacity;
    // 头插法
    curr->next = new_table[idx];
    new_table[idx] = curr;
}

static void grow_capacity(Configuration* map)
{
    int new_capacity = (map->capacity < DEFAULT_CAPACITY) ?
        DEFAULT_CAPACITY : (map->capacity * 2);
    // 创建 new_table，注意：这里我们应该使用的是 calloc
    Entry** new_table = (Entry**)calloc(new_capacity, sizeof(Entry*));
    // 重新设置哈希种子
    uint32_t seed = rand();
    // 将所有结点重新映射到新数组中
    if (map->size) {
        for (size_t i = 0; i < map->capacity; i++) {
            Entry* curr = map->table[i];     /* 获取链表的第一个结点 */
            while (curr) {
                Entry* next = curr->next;    /* 保存下一个结点 */
                // 重新映射 curr 结点
                rehash(curr, new_table, new_capacity, seed);
                curr = next;
            }
        }
        free(map->table);   /* 销毁旧的 table */
    }
    // 更新哈希表的信息
    map->table = new_table;
    map->capacity = new_capacity;
    map->hashseed = seed;
}

/* 添加键值对(key,val)，如果key已存在，则替换key关联的值 */
void configuration_put(Configuration* map, K key, V val)
{
    // 安全检查：如果 table 为 NULL，则扩充为 DEFAULT_CAPACITY 大小
    if (map->table == NULL) {
        grow_capacity(map);
    }
    // 1. 对 key 进行哈希，判断 key 位于哪一条链表中 (哈希桶)
    int idx = hash(key, strlen(key), map->hashseed) % map->capacity;
    // 2. 遍历链表
    Entry* curr = map->table[idx];   /* 获取链表的第一个结点 */
    while (curr) {
        if (strcmp(curr->key, key) == 0) {  /* 找到了 key */
            // 更新 key 关联的 val，并把原来的 val 返回
            free(curr->val);
            curr->val = strdup(val);
            return ;
        }
        curr = curr->next;
    } // curr == NULL, key 不存在

    // 3. 添加 key-val 键值对
    // 判断是否需要扩容
    if (map->size >= map->capacity * LOAD_FACTOR) {
        grow_capacity(map);
        // 注意：扩容之后需要重新计算 key 在哈希表中的位置
        idx = hash(key, strlen(key), map->hashseed) % map->capacity;
    }

    Entry* new_entry = (Entry*)malloc(sizeof(Entry));   /* 创建结点 */
    // 初始化结点
    new_entry->key = strdup(key);
    new_entry->val = strdup(val);
    // 采用头插法，将新的结点插入到对应的链表 (哈希桶)
    new_entry->next = map->table[idx];
    map->table[idx] = new_entry;

    map->size++;    /* 结点数目加 1 */
}

/* 根据key获取值 */
V configuration_get(Configuration* map, K key)
{
    if (!map->table) {
        return NULL;
    }
    // 计算 key 在哈希表中的位置
    int idx = hash(key, strlen(key), map->hashseed) % map->capacity;
    Entry* curr = map->table[idx];   /* 获取链表第一个结点 */
    while (curr) {
        if (strcmp(curr->key, key) == 0) {  /* 找到 key 了 */
            return strdup(curr->val);
        }
        curr = curr->next;
    }   /* curr == NULL, key 不存在 */
    return NULL;
}

/* 如果key存在，则删除键值对 */
void configuration_delete(Configuration* map, K key)
{
    if (!map->table) {
        return ;
    }
    // 计算 key 在哈希表中的位置
    int idx = hash(key, strlen(key), map->hashseed) % map->capacity;
    Entry* prev = NULL; 
    Entry* curr = map->table[idx];   /* 获取链表第一个结点 */
    while (curr) {
        if (strcmp(curr->key, key) == 0) {  /* 找到 key 了 */
            // 删除 curr 结点
            if (prev == NULL) {
                map->table[idx] = curr->next;
            } else {
                prev->next = curr->next;
            }
            free(curr->key);
            free(curr->val);
            free(curr);
            map->size--;    /* 更新 map->size */
            return;
        }
        prev = curr;
        curr = curr->next;
    }   // curr = NULL, key 不存在
}

void configuration_display(const Configuration* map)
{
    printf("{ ");
    if (map->size != 0) {
        size_t size = map->size;
        for (size_t i = 0; i < map->capacity; i++) {
            Entry* curr = map->table[i];
            while (curr) {
                if (--size) {
                    printf("%s=%s, ", curr->key, curr->val);
                } else {
                    printf("%s=%s ", curr->key, curr->val);
                }
                curr = curr->next;
            }
        }
    }
    printf("}\n");
}

#ifdef CONFIGURATION_TEST
int main(int argc, char* argv[]) {
    Configuration conf;
    configuration_init(&conf);

    configuration_load(&conf, "CloudDisk.ini");
    configuration_display(&conf);

    configuration_destroy(&conf);
    return 0;
}
#endif
